#include <string>
#include <unordered_set>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

class Solution {
    public:
        vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
            vector<string> result_vector;
            const string saved_find_result = "";
            if (!s.empty() && s.length() > 0 && !s.empty()) {
                if (this->checkFromFoot(s, wordDict)) {
                    this->findWordFromHead(s, wordDict, 1, saved_find_result, result_vector); 
                }
            }
            return result_vector; 
        }

        // non recursive for wordbreak
        
        //        //return the index of the word , return -1 if not find
        bool findWordFromHead(const string &str, const unordered_set<string>& wordDict, const int pos, const string &saved_find_result, vector<string> &result_vector) {
            cout << "str:" << str << "\tpos:" << pos << "\tsaved_find_result:" << saved_find_result << endl;
            if (str.empty() || wordDict.empty() || pos <= 0) {
                cerr << "str=" << str << "\t wordDict=" << wordDict.empty()<< "\t  saved_find_result="<< saved_find_result << endl;                 
                return false;
            } else {
                // para is right
                int len_str = str.length();
                if (len_str == 0) {
                    //cout << "sub_str length is 0" << endl; 
                    return false;
                } else if (pos == len_str) {
                    if (wordDict.find(str) != wordDict.end()) {
                        string tem_saved_find_result = saved_find_result  + str; 
                        //cout << "saved_find_result="<< tem_saved_find_result<< endl;
                        result_vector.push_back(tem_saved_find_result);
                        return true;
                    } else {
                        //cout << "can't find suitable result" << endl;
                        return false;
                    }
                } else {
                    string sub_str = str.substr(0, pos);
                    auto find_result = wordDict.find(sub_str);
                    if (find_result != wordDict.end()) {
                        string tem_saved_find_result = saved_find_result + sub_str + " ";
                        //cout << "sub_str" << sub_str<< "\tsaved_find_result:" << saved_find_result  << endl;
                        findWordFromHead(str.substr(pos, len_str - pos), wordDict, 1, tem_saved_find_result, result_vector);
                    } 
                    if (pos + 1 <= len_str) {
                        string tem_saved_find_result = saved_find_result;
                        findWordFromHead(str, wordDict, pos + 1, tem_saved_find_result, result_vector);
                    }
                }
                return true;
            } 
        }
        bool checkFromFoot(const string &str, const unordered_set<string> &wordDict) {
            int len_str = str.length();
            if (!str.empty() && len_str > 0) {
                for (int i = 1; i <= len_str; ++i) {
                    string tem_sum_str = str.substr(len_str - i, i); 
                    auto find_result = wordDict.find(tem_sum_str);  
                    if (find_result != wordDict.end()) {
                        return true; 
                    }
                } 
            }
            return false; 
        } 

        //        bool findWordFromQueue(const string &str, queue<int> *queue_index, stack<int> *stack_index) {
        //            if (stack_index == NULL || queue_index == NULL) {
//                return false;
//            }
//            if (!queue_index->empty()) {
//                stack_index->push(queue_index.front());
//                queue_index.pop();
//                 
//            }
//        
//        }
};
int main() {
    //cout << "Hello" << endl;
    //std::unordered_set<int> example = {1, 2, 3, 4};

    //auto search = example.find(2);
    //if(search != example.end()) {
    //        std::cout << "Found " << (*search) << '\n';
    //}
    //else {
    //        std::cout << "Not found\n";
    //} 
//// test data 1
//    string s = "catsanddog";
//    unordered_set<string> wordDict;
//    wordDict.insert("cat");
//    wordDict.insert("cats");
//    wordDict.insert("and");
//    wordDict.insert("sand");
//    wordDict.insert("dog");
// test data 2 
    string s = "a";
    unordered_set<string> wordDict;
    wordDict.insert("a");
 
    Solution solu;
//    solu.wordBreak(s, wordDict);
    string saved_find_result = "";
    vector<string> result_vector;
    //solu.findWordFromHead(s, wordDict, 1, saved_find_result, result_vector);
    result_vector = solu.wordBreak(s, wordDict); 
    for (auto result : result_vector) {
        cout << result << endl;
    }
    return 0;
}
